package com.LeeCode;

/**
 * 对链表进行插入排序
 */

public class Code147 {
    public static void main(String[] args) {
        int[] arr = {1, 5, 3, 4, 0};
        ListNode head = Utils.arrayToListNode(arr);
        Utils.printListNode(new Code147().insertionSortList(head));
    }

    public ListNode insertionSortList(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        ListNode target, cur = head;
        while (cur != null) {
            target = dummyHead;
            while (target.next != null && target.next.val < cur.val) {
                target = target.next;
            }
            ListNode temp = cur;
            cur = cur.next;
            temp.next = target.next;
            target.next = temp;
        }
        return dummyHead.next;
    }
}
